package features.advance.leetcode.tree.easy;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 404. 左叶子之和
 * 计算给定二叉树的所有左叶子之和。
 *
 * 示例：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 *
 *
 * @author LIN
 * @date 2021-04-19
 */
public class Solution404 {

    public int sumOfLeftLeaves(TreeNode root) {
        return root != null ? dfs(root) : 0;
    }

    /**
     *  深度优先搜索
     * @param node
     * @return
     */
    public int dfs(TreeNode<Integer> node) {
        int ans = 0;
        if (node.left != null) {
            ans += isLeafNode(node.left) ? node.left.getVal() : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
            ans += dfs(node.right);
        }
        return ans;
    }

    /**
     *
     *  广度优先搜索
     * @param node
     * @param dummy
     * @return
     */
    public int dfs(TreeNode node,boolean dummy){
        int ans = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);

        while(!queue.isEmpty()) {
            TreeNode<Integer> poll = queue.poll();
            if(poll.left != null){
                if (isLeafNode(poll.left)){
                    ans +=poll.left.getVal();
                }else{
                    queue.add(poll.left);
                }

            }
            if (poll.right != null){
                if (isLeafNode(poll.right)){
//                            ans +=poll.right.getVal();
                }else{
                    queue.add(poll.right);
                }
            }

        }


        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
        return node.left == null && node.right == null;
    }


    public static void main(String[] args) {
        String str = "[3,9,20,1,null,15,7]";
        TreeNode treeNode = TreeUtil.parseArray(str);
        int dfs = new Solution404() {
            @Override
            public int sumOfLeftLeaves(TreeNode root) {
                return super.sumOfLeftLeaves(root);
            }
        }.sumOfLeftLeaves(treeNode);
        System.out.println(dfs);
    }
}
